package top.fengleifeng.question;

/**
 * @program: leetcode-test
 * @description: 给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。
 * <p>
 * 注意：
 * 数组大小可能非常大。 使用太多额外空间的解决方案将不会通过测试。
 * <p>
 * 示例:
 * <p>
 * int[] nums = new int[] {1,2,3,3,3};
 * Solution solution = new Solution(nums);
 * <p>
 * // pick(3) 应该返回索引 2,3 或者 4。每个索引的返回概率应该相等。
 * solution.pick(3);
 * <p>
 * // pick(1) 应该返回 0。因为只有nums[0]等于1。
 * solution.pick(1);
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/random-pick-index
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author: fengleifeng
 * @create: 2020-08-11 10:56
 **/
public class Num398随机数索引 {

}

/**
 * 蓄水池抽样问题
 * 首先从最简单的例子出发：数据流只有一个数据。我们接收数据，发现数据流结束了，直接返回该数据，该数据返回的概率为1。
 * <p>
 * 看来很简单，那么我们试试难一点的情况：假设数据流里有两个数据。我们读到了第一个数据，这次我们不能直接返回该数据，
 * 因为数据流没有结束。我们继续读取第二个数据，发现数据流结束了。因此我们只要保证以相同的概率返回第一个或者第二个数据就可
 * 以满足题目要求。因此我们生成一个0到1的随机数R,如果R小于0.5我们就返回第一个数据，如果R大于0.5，返回第二个数据。
 * <p>
 * 接着我们继续分析有三个数据的数据流的情况。为了方便，我们按顺序给流中的数据命名为1、2、3。我们陆续收到了数据1、2和前
 * 面的例子一样，我们只能保存一个数据，所以必须淘汰1和2中的一个。应该如何淘汰呢？不妨和上面例子一样，我们按照二分之一
 * 的概率淘汰一个，例如我们淘汰了2。继续读取流中的数据3，发现数据流结束了，我们知道在长度为3的数据流中，如果返回数据
 * 3的概率为1/3,那么才有可能保证选择的正确性。也就是说，目前我们手里有1,3两个数据，我们通过一次随机选择，以1/3的概
 * 率留下数据3，以2/3的概率留下数据1。那么数据1被最终留下的概率是多少呢？
 * <p>
 * 数据1被留下：（1/2）(2/3) = 1/3
 * 数据2被留下概率：（1/2）(2/3) = 1/3
 * 数据3被留下概率：1/3
 * 这个方法可以满足题目要求，所有数据被留下返回的概率一样！
 * <p>
 * 因此，我们做一下推论：
 * <p>
 * 假设当前正要读取第n个数据，则我们以1/n的概率留下该数据，否则留下前n-1个数据中的一个。
 */
class Solution2 {
    int[] data;

    public Solution2(int[] nums) {
        this.data = nums;
    }

    public int pick(int target) {
        int result=0;
        boolean fullData = false;
        int count = 0;
        int reachCount = 0;

        while (count < data.length) {
            if (target == data[count]) {
                if (!fullData) {//初始化数据
                    result = count;
                } else {
                    //获取随机数
                }
            }
        }
        return result;
    }
}
